package hdoj;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class MazeHDU1026 {

	private static final int[][] dir = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
	
	private static final char OBSTACLE = 'X';
	
	private static final int MAX = 102;
	
	private int minMinute;
	
	private int rows, columns;
	
	private char[][] maze = new char[MAX][MAX];
	private char[][] copy = new char[MAX][MAX];
	private boolean[][] visited = new boolean[MAX][MAX];
	
	private int[][] way = new int[MAX][MAX];    //记录路径
	
	public static Comparator<Node> nodeComparator = new Comparator<Node>(){
		 
        @Override
        public int compare(Node c1, Node c2) {
            return (int) (c1.minute - c2.minute);
        }
    };
	
	//迷宫中有.和数字以及X，  .表示通路，经过.只需耗费1s
	//数字表示还需耗费额外的时间来通过该位置
	//这道题还需要记录路径
	public static void main(String[] args) {
		MazeHDU1026 object = new MazeHDU1026();
		object.getRes();
	}
	
	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			minMinute = 0;
			rows = scanner.nextInt();
			columns = scanner.nextInt();
			for(int i = 0; i < rows; i++){
				maze[i] = scanner.next().toCharArray();
			}
//			bfs(0, 0);
			bfsPriorityQueue(0, 0);
			if(minMinute != 0){
				Node[] nodeArray = new Node[minMinute + 1];
				for(int i = 0; i <= minMinute; i++){
					nodeArray[i] = new Node();
				}
				int curX = rows - 1, curY = columns - 1;
				for(int i = minMinute; i >= 0; i--){
					nodeArray[i].x = curX;
					nodeArray[i].y = curY;
					int num = 0;
					//如果该位置有怪物 
					if(maze[curX][curY] >= '1' && maze[curX][curY] <= '9'){
						num = maze[curX][curY] - '0';
					}
					for (int j = num; j >= 1; j--) {
						nodeArray[i - j].x = curX;
						nodeArray[i - j].y = curY;
					}
					if(num != 0){
						i -= num;
					}
					//way[curX][curY]记录的是上一步的方向
					switch (way[curX][curY]) {
					case 0:
						curY += 1;
						break;
					case 1:
						curX += 1;
						break;
					case 2:
						curY -= 1;
						break;
					case 3:
						curX -= 1;
						break;
					default:
						break;
					}
				}
				System.out.println("It takes " + minMinute + " seconds to reach the target position," +
						" let me show you the way.");
				for (int i = 1; i <= minMinute; i++) {
					System.out.println(i + "s:(" + nodeArray[i - 1].x + ',' + nodeArray[i - 1].y
							+ ")->(" + nodeArray[i].x + ',' + nodeArray[i].y + ')');
					curX = nodeArray[i].x;
					curY = nodeArray[i].y;
					if(maze[curX][curY] >= '1' && maze[curX][curY] <= '9'){
						int num = maze[curX][curY] - '0';
						for(int j = 1; j <= num; j++){
							System.out.println( (i + j) + "s:FIGHT AT (" + nodeArray[i].x + "," + 
									nodeArray[i].y + ")");
						}
						i += num;
					}
				}
				System.out.println("FINISH");
			}else{
				System.out.println("God please help our poor hero.");
				System.out.println("FINISH");
			}
		}
		scanner.close();
	}
	
	
	private class Node{
		int x; int y;
		int minute;
		public Node() {
		}
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	//广度优先搜索的难点在于此时由于怪物的HP，我们对有怪物或者没怪物的处理肯定不一样
	//看的博客，思路是遇到怪兽的时候，我们先不移动，而是将怪兽的HP减1，直至减为0，我们先看看到底该怎么做
	//Runtime 421MS
	public void bfs(int x, int y){
		Queue<Node> queue = new LinkedList<>();
		Node temp = new Node(x, y);
		queue.add(temp);
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < columns; j++) {
				visited[i][j] = false;
				copy[i][j] = maze[i][j];
			}
		}
		visited[x][y] = true;
		while(!queue.isEmpty()){
			temp = queue.poll();
			//到达终点
			if(temp.x == rows - 1 && temp.y == columns - 1){
				minMinute = temp.minute;
				if(Character.isDigit(copy[temp.x][temp.y])){
					minMinute += copy[temp.x][temp.y] - '0';
				}
				return;
			}
			if(copy[temp.x][temp.y] >= '1' && copy[temp.x][temp.y] <= '9'){
				if(copy[temp.x][temp.y] == '1'){
					copy[temp.x][temp.y] = '.';
				}else{
					copy[temp.x][temp.y]--;
				}
				Node next = new Node();
				next.minute = temp.minute + 1;
				next.x = temp.x;
				next.y = temp.y;
				queue.add(next);
				continue;
			}
			for(int i = 0; i < dir.length; i++){
				int curX = temp.x + dir[i][0];
				int curY = temp.y + dir[i][1];
				if(curX < 0 || curX >= rows || curY < 0 || curY >= columns || copy[curX][curY] == OBSTACLE
						|| visited[curX][curY]){
					continue;
				}
				Node next = new Node();
				next.minute = temp.minute + 1;
				//如果我们遇到了怪兽，我们不急着移动，将HP减1
//				if(copy[curX][curY] >= '1' && copy[curX][curY] <= '9'){
//					if(copy[curX][curY] == '1'){
//						copy[curX][curY] = '.';
//					}else{
//						copy[curX][curY]--;
//					}
//					next.x = temp.x;
//					next.y = temp.y;
//				}else{
					next.x = curX;
					next.y = curY;
					way[curX][curY] = i;
					//注意，只有进入了才设置为true，如果是怪兽，因为此时还没有进入该位置，所以不设为true
					visited[curX][curY] = true;
//				}
				queue.add(next);
			}
		}
	}

	
	// Runtime 374MS
	//使用优先级队列
	public void bfsPriorityQueue(int x, int y){
		PriorityQueue<Node> queue = new PriorityQueue<>(nodeComparator);
		Node temp = new Node(x, y);
		queue.add(temp);
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < columns; j++) {
				visited[i][j] = false;
			}
		}
		visited[x][y] = true;
		while(!queue.isEmpty()){
			temp = queue.poll();
			if(temp.x == rows - 1 && temp.y == columns - 1){
				minMinute = temp.minute;
				return;
			}
			for(int i = 0; i < dir.length; i++){
				int curX = temp.x + dir[i][0];
				int curY = temp.y + dir[i][1];
				if(curX < 0 || curX >= rows || curY < 0 || curY >= columns || maze[curX][curY] == OBSTACLE
						|| visited[curX][curY]){
					continue;
				}
				Node next = new Node(curX, curY);
				next.minute = temp.minute + 1;
				if(maze[curX][curY] >= '1' && maze[curX][curY] <= '9'){
					next.minute += maze[curX][curY] - '0';
				}
				way[curX][curY] = i;
				visited[curX][curY] = true;
				queue.add(next);
			}
		}
	}
}
